#include <iostream>
#include <queue>
#include <cassert>

using namespace std;

template <typename Key, typename Value>
class BST{
	private:
		struct Node{
			Key key;
			Value value;
			Node *left;		// 左右两个孩子,指向node的指针
			Node *right;

			Node(Key key, Value value){
				this->key = key;
				this->value = value;
				this->left = this->right = NULL;
			}
		};

		Node *root;		// 根节点
		int count;		// 一共有多少个节点,存了多少数据
	public:
		BST(){
			root = NULL;
			count = 0;
		}

		~BST(){					// 使用后序遍历,将每一个节点逐渐释放空间
			destory(root);
		}

		int size(){
			return count;
		}

		bool isEmpty(){
			return count == 0;
		}

		void insert(Key key, Value value){
			root = insert(root, key, value);
		}

		bool contain(Key key){
			return contain(root, key);
		}

		Value* search(Key key){
			return search(root, key);
		}

		void preOrder(){		// 前序遍历 自身->左->右
			preOrder(root);
		}

		void inOrder(){	   // 中序遍历	左->自身->右
			inOrder(root);
		}

		void postOrder(){	   // 后序遍历	左->右->自身
			postOrder(root);
		}

		void levelOrder(){		// 层序遍历 广度优先遍历
			queue<Node*> q;
			q.push(root);
			while(!q.empty()){
				Node *node = q.front();
				q.pop();

				cout << node->key << endl;

				if(node->left){
					q.push(node->left);
				}

				if(node->right){
					q.push(node->right);
				}
			}
		}

		Key minimum(){				// 寻找最小键值
			assert(count != 0);
			Node* minNode = minimum(root);
			return minNode->key;
		}

		Key maximum(){				// 寻找最大键值
			assert(count != 0);
			Node* maxNode = maximum(root);
			return maxNode->key;
		}

		void removeMin(){			// 删除最小值节点
			if(root){				// 根不为空
				root = removeMin(root);
			}
		}

		void removeMax(){			// 删除最大值节点
			if(root){
				root = removeMax(root);
			}
		}

		// O(logN)
		void remove(Key key){		// 删除键值为 key节点
			root = remove(root, key);
		}

	private:
		/**
		 * 向以node为根的二叉搜索树中,插入节点(key, value)
		 * 返回插入新节点后的二叉搜索树的根
		 */
		Node* insert(Node *node, Key key, Value value){
			if(node == NULL){
				count++;
				return new Node(key, value);
			}

			if(key == node->key)
				node->value = value;
			else if(key < node->key)
				node->left = insert(node->left, key, value);
			else
				node->right = insert(node->right, key, value);

			return node;
		}

		// 查看以node为根的二叉搜索树中是否包含键值为key的节点
		bool contain(Node* node,Key key){
			if(node == NULL){
				return false;
			}

			if(key == node->key)
				return true;
			else if(key < node->key)
				return contain(node->left, key);
			else	// key > node->key
				return contain(node->right, key);
		}

		Value* search(Node* node, Key key){
			if(node == NULL){
				return NULL;
			}

			if(key == node->key){
				return &(node->value);		// 返回value 对应的地址
			}else if(key < node->key){
				return search(node->left, key);
			}else{
				return search(node->right, key);
			}
		}

		void preOrder(Node* node){
			if(node != NULL){
				cout << node->key << endl;
				preOrder(node->left);
				preOrder(node->right);
			}
		}

		void inOrder(Node* node){
			if(node != NULL){
				inOrder(node->left);
				cout << node->key << endl;
				inOrder(node->right);
			}
		}

		void postOrder(Node* node){
			if(node != NULL){
				postOrder(node->left);
				postOrder(node->right);
				cout << node->key << endl;
			}
		}

		void destory(Node* node){
			if(node != NULL){
				destory(node->left);
				destory(node->right);
				delete node;
				count--;
			}
		}

		// 在以node为根的二叉搜索树中,返回最小键值的节点
		Node* minimum(Node* node){
			if(node->left == NULL){
				return node;
			}
			return minimum(node->left);
		}

		// 在以node为根的二叉搜索树中,返回最大键值的节点
		Node* maximum(Node* node){
			if(node->right == NULL){
				return node;
			}
			return maximum(node->right);
		}
		
		/**
		 * 删除掉以node为根的二分搜索树中的最小节点
		 * 返回删除节点后新的二分搜索树的根
		 */
		Node* removeMin(Node* node){
			if(node->left == NULL){		// 如果存在右节点,代替当前节点
				Node* rightNode = node->right;
				delete node;
				count--;
				return rightNode;
			}
			node->left = removeMin(node->left);		// 以左孩子为根的二分查找树继续查找
			return node;
		}

		/**
		 * 删除掉以node为根的二分搜索树中的最小节点
		 * 返回删除节点后新的二分搜索树的根
		 */
		Node* removeMax(Node* node){
			if(node->right == NULL){
				Node* leftNode = node->left;
				delete node;
				count--;
				return leftNode;
			}
			node->right = removeMax(node->right);
			return node;
		}

		/**
		 * 最小值所在节点只会有右孩子  删除最小值类似于 删除只有右孩子节点
		 * 最大值所在节点只会有左孩子  删除最大值类似于 删除只有左孩子节点
		 * 如果只有左孩子，左孩子代替当前节点,如果只有右孩子,右孩子代替当前节点
		 * 如果有左右孩子, 将右节点的最小值代替当前要删除节点 s = min(d->right)
		 * 删除掉以node为根的二分搜索树中键值为key的节点
		 * 返回删除节点后新的二分搜索树的根
		 */
		Node* remove(Node* node, Key key){
			if(node == NULL){			// 没有键值为key的节点
				return NULL;
			}

			if(key < node->key){		// 小于当前节点在其左孩子中查找
				node->left = remove(node->left, key);
				return node;
			}else if(key > node->key){
				node->right = remove(node->right, key);
			}else{		// key == node->key
				if(node->left == NULL){					// 只有右孩子
					Node* rightNode = node->right;
					delete node;
					count--;
					return rightNode;
				}

				if(node->right == NULL){			   // 只有左孩子
					Node* leftNode = node->left;
					delete node;
					count--;
					return leftNode;
				}

				assert(node->left != NULL && node->right != NULL);

				// ** 根据右子树最小节点重新建立一个节点,不然后面删除这里指向失败
				Node* successor = new Node(minmum(node->right));
				count++;

				successor->right = removeMin(node->right);	// 删除d的右子树最小节点,返回删除子树的根节点(删除59,返回60)同时将s的右节点指向右子树最小节点
				successor->left = node->left;	// s节点左孩子就是被删除节点d的左孩子

				delete node;
				count--;
				return successor;


			}
		}
};
